package Queue;

import java.util.PriorityQueue;

/**
 * @Classname JZ41数据流中的中位数
 * @Description TODO
 * @Date 2023/3/7 20:12
 * @Created by xjl
 */
public class JZ41数据流中的中位数 {
    /**
     * @description 数据流中的中位数
      * @param: null
     * @date: 2023/3/7 20:18
     * @return:
     * @author: xjl
    */
    class MedianFinder {
        PriorityQueue<Integer> queMin;
        PriorityQueue<Integer> queMax;

        public MedianFinder() {
            // 设置两个队列queueMin 是从大到小的顺序
            queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
            // 是从小到大的顺序
            queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
        }

        public void addNum(int num) {
            queMax.add(num);
            queMin.add(queMax.poll());
            // 保持max堆中的个数》=min中的个数
            if (queMax.size()<queMin.size()){
                queMax.add(queMin.poll());
            }
        }

        public double findMedian() {
            // 如果是奇数个数 那就返回
            if (queMax.size() > queMin.size()) {
                return queMax.peek();
            }
            return (queMin.peek() + queMax.peek()) / 2.0;
        }
    }
}
